This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Exponentiation may be expressed as the general problem of evaluating y=gd in a (multiplicatively written) group G, where gεG and dεZ>0. The neutral element in G is denoted 1G. The m-ary expansion of d is given by
      d    =                  ∑                  i          =          0                          I          -          1                    ⁢                        d          i                ⁢                  m          i                      ,with 0≦di≦m and dI-1≠0. Integer I=I(m) represents the number of digits (in radix m) for the m-ary representation of d and is called the m-ary length of d.Left-to-Right Algorithms
The most widely used exponentiation algorithm is the binary method (also known as the “square-and-multiply” algorithm). It relies on the simple observation that gd=(gd/2)2 if d is even and gd=(g(d-1)/2)2·g if d is odd.
The binary method extends easily to any radix m. Let
      H    i    =            ∑              j        =        i                    I        -        1              ⁢                  d        j            ⁢                        m                      j            -            i                          .            Since
            H      i        =                            (                                    ∑                              j                =                                  i                  +                  1                                                            I                -                1                                      ⁢                                          d                j                            ⁢                              m                                  j                  -                  i                                                              )                +                  d          i                    =                        m          ⁢                                          ⁢                      H                          i              +              1                                      +                  d          i                      ,we get
      g          H      i        =      {                                                      (                              g                                  H                                      i                    +                    1                                                              )                        m                                                              if              ⁢                                                          ⁢                              d                i                                      =            0                                                                                          (                                  g                                      H                                          i                      +                      1                                                                      )                            m                        ·                          g                              d                i                                                              otherwise                    
Noting that gd=gH0, the previous relation gives rise to an exponentiation algorithm. It can be readily programmed by scanning the m-ary representation of d from left to right. As, at iteration i, for I−2≧i≧0, the method requires a multiplication by gdi when di≠0, the values of gt with 1≦t≦m−1 are pre-computed and stored in (m−1) temporary variables; namely, R[j]←gj for 1≦j≦m−1. If the successive values of gHi are kept track of in an accumulator A, one gets, for I−2≧i≧0:
  A  ←      {                                        A            m                                                              if              ⁢                                                          ⁢                              d                i                                      =            0                                                                          A              m                        ·                          R              ⁡                              [                                  d                  i                                ]                                                              otherwise                    where A is initialized to R[dI-1]. The algorithm is referred to as the (left-to-right) m-ary algorithm.Right-to-Left Algorithms
A similar algorithm may be based on the right-to-left scan of exponent d. This may be useful when the m-ary length of d is unknown in advance. In the binary case, i.e. when m=2, the binary expansion of d is
  d  =            ∑              i        =        0                    I        -        1              ⁢                  d        i            ⁢                        2          i                .            
The algorithm makes use of the relation
      g    d    =            ∏              0        ≤        i        ≤                  I          -          1                      ⁢          g              2        i            for di≠0. An accumulator A is initialized to g and squared at each iteration, i.e. it contains g2i at iteration i. Another accumulator, R[1], initialized to 1G, is multiplied with A if di≠0. Hence, at iteration I−1, if di≠0, accumulator R[1] contains the value of
            ∏                        0          ≤          i          ≤                      I            -            1                                                d            i                    ≠          0                      ⁢          g              2        i              =            g      d        .  
Although less known than its left-to-right counterpart, the algorithm can be extended to higher radixes. The basic idea remains the same. If
  d  =            ∑              i        =        0                    I        -        1              ⁢                  d        i            ⁢              m        i            denotes the m-ary expansion of d, it is possible to express it as:
            g      d        =                                        ∏                          0              ≤              i              ≤                              I                -                1                                                                        d              i                        =            1                          ⁢                              g                          m              i                                ·                                                    ∏                                  0                  ≤                  i                  ≤                                      I                    -                    1                                                                                                d                  i                                =                2                                      ⁢                                          g                                  2                  ⁢                                      m                    i                                                              ⁢                                                          ⁢              …              ⁢                                                          ⁢                                                                    ∏                                          0                      ≤                      i                      ≤                                              I                        -                        1                                                                                                                        d                      i                                        =                                          m                      -                      1                                                                      ⁢                                  g                                                            (                                              m                        -                        1                                            )                                        ⁢                                          m                      i                                                                                                              =                        ∏                      j            =            1                                m            -            1                          ⁢                              (                          L              j                        )                    j                      ,          ⁢            where      ⁢                          ⁢              L        j              =                            ∏                                    0              ≤              i              ≤                              I                -                1                                                                    d                i                            =              j                                      ⁢                              g                          m              i                                ⁢                                          ⁢          for          ⁢                                          ⁢                      d            i                              =              j        .            
Hence, using (m−1) accumulators, R[1] . . . R[m−1], to keep track of the values of Lj, 1≦m−1, and an accumulator A that stores the successive values gmi at iteration i, the accumulators are updated, for 1≦i≦I−1, as
  {                                                        R              ⁡                              [                                  d                  i                                ]                                      ←                                          R                ⁡                                  [                                      d                    i                                    ]                                            ·              A                                                                          if              ⁢                                                          ⁢                              d                i                                      ≠            0                                                            A            ←                          A              m                                                otherwise                         where A is initialized to g and R[1] . . . R[m−1] are initialized to 1G. It can be seen that gd is then given by
  A  ←            ∏              j        =        1                    m        -        1              ⁢                            R          ⁡                      [            j            ]                          j            .      
The obtained algorithm is referred to as the right-to-left m-ary algorithm.
It will however be appreciated that an exponentiation algorithm that is not properly implemented may be vulnerable to different kinds of attacks, such as side-channel attacks and fault attacks. Simple Power Analysis (SPA) attacks and safe-error attacks are particularly relevant for exponentiation algorithms.
By observing a suitable side channel, such as the power consumption or electromagnetic emanations, an attacker may recover secret information. For exponentiation-based cryptosystems, the goal of the attacker is to recover the value of exponent d (or a part thereof) used in the computation of gd. SPA-type attacks assume that the attacker infers secret information—typically one or several bits of d—from a single execution of gd.
This may be exemplified by the square-and-multiply algorithm, i.e. a left-to-right algorithm with m=2.
            Input      ⁢              :            ⁢                          ⁢      g        ∈    G    ,      d    =                  ∑                  i          =          0                          I          -          1                    ⁢                        d          i                ⁢                  2          i                    
Output: gd 
1. R[1]←g; A←1G 
2. for i=I−1 down to 0 do
3. A←A2 
4. if (di≠0) then A←A·R[1]
5. end
6. return A
Each iteration comprises a ‘square’ and, when the bit exponent is non-zero, a subsequent ‘multiply’. Since the algorithm behaves differently depending on the bit values of the exponent, this may be observed from a suitable side-channel. The information thus gleaned may enable the attacker to recover one or more bits of exponent d.
One way of preventing an attacker from recovering the bit values is to execute the same instructions regardless of the value of di. Such an algorithm is said to be ‘regular’ and there are several different implementations.                The test of whether a digit is non-zero in step 4 may be removed by replacing the step by A←A·R[di], where temporary variable R[0] is initialized to 1G. Alternatively, a fake multiply may be performed when di=0. Doing so, there will be no conditional branchings; each iteration comprises a square followed by a multiply. This is known as the ‘square-and-multiply-always’ algorithm. However, the resulting algorithm is vulnerable to safe-error attacks.        A regular exponentiation may also be obtained by recoding exponent d such that none of the digits are zero, but this supposes that the recoding algorithm itself is resistant against SPA-type attacks.        
It will be appreciated that while the square-and-multiply algorithm was used as an example, the attacks mentioned apply to the m-ary exponentiation algorithms already described. While it may be argued that, for larger m, m-ary exponentiation algorithms are more regular and therefore more resistant against SPA-type attacks, these algorithms are not entirely regular, since two cases are to be distinguished: di=0 and di≠0.
A safe-error attack, already mentioned in passing, is made by inducing a fault during the execution of an instruction. An attacker may deduce that the instruction was fake if the final result is correct and, inversely, that the instruction was effective if the final result is incorrect. This knowledge may then be used to obtain a bit of the exponent d.
In the square-and-multiply-always algorithm, the attacker can induce a fault during a multiply. If the final result is correct, then the attacker may deduce that the corresponding exponent bit is a zero (i.e. fake multiply); otherwise, the attacker may deduce that the exponent bit is a one.
Safe-error attacks also apply similar higher-radix m-ary algorithms to distinguish digits equal to zero.
In the prior art, there are highly regular exponentiation algorithms whose characteristics are:                they are regular, i.e. they always repeat the same instructions in the same order regardless of the input        they do not insert any dummy operations.        
Such highly regular algorithms protect against SPA-type attacks and safe-error attacks. Examples of such algorithms include the so-called Montgomery ladder and a more recent powering ladder.
The Montgomery ladder has been described by Marc Joye and Sung-Ming Yen in “The Montgomery Powering Ladder”, in B. S. Kaliski Jr., . K. Koç, and C. Paar, editors, Cryptographic Hardware and Embedded Systems—CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages 291-302, Springer-Verlag, 2002.
            Input      ⁢              :            ⁢                          ⁢      g        ∈    G    ,      d    =                  ∑                  i          =          0                          I          -          1                    ⁢                        d          i                ⁢                  2          i                    
Output: gd 
1. R[0]←1G; R[1]←g
2. for i=I−1 down to 0 do
3. R[1−di]←R[1−di]·R[di]
4. R[di]←R[di]2 
5. end
6. return R[0]
The more recent powering ladder was described by Marc Joye in “Highly Regular Right-to-Left Algorithms for Scalar Multiplication”, in P. Paillier and I. Verbauwhede, editors, Cryptographic Hardware and Embedded Systems—CHES 2007, volume 4727 of Lecture Notes in Computer Science, pages 135-147, Springer-Verlag, 2007.
            Input      ⁢              :            ⁢                          ⁢      g        ∈    G    ,      d    =                  ∑                  i          =          0                          I          -          1                    ⁢                        d          i                ⁢                  2          i                    
Output: gd 
1. R[0]←1G; R[1]←g
2. for i=0 to I−1 do
3. R[1−d]←R[1−di]2·R[di]
4. end
5. return R[0]
As will be noticed, both algorithms rely on specific properties of the binary representation.
It can therefore be appreciated that there is a need for a solution that provides a highly regular algorithm that may be used for radixes higher than 2 or that offer other characteristics. This invention provides such a solution.